In many environments, a large amount of data can be or has been collected which records experience over time within the environment. For example, a healthcare environment may record clinical data, diagnoses and treatment regimens for a large number of patients, as well as outcomes. A Smart Electrical Grid environment might record information about the behaviors of suppliers and consumers. A business environment may record customer information such as who they are and what they do, and their browsing and purchasing histories in order to target advertisements or predict future transactions. A computer security environment may record a large number of software code examples that have been found to be malicious. A financial asset trading environment may record historical price trends and related statistics about numerous financial assets (e.g., securities, indices of stock markets such as stock price, currencies) over a long period of time (e.g., moving average of a stock price over 30 minutes). Despite the large quantities of such data, or perhaps because of it, deriving useful knowledge from such data stores can be a daunting task.
The process of extracting patterns from such data sets is known as data mining. Many techniques have been applied to the problem, but the present discussion concerns a class of techniques known as genetic algorithms. Genetic algorithms can be applied to all of the above-mentioned environments.
Evolutionary algorithms, which are supersets of Genetic Algorithms, are good at traversing chaotic search spaces. According to Koza, J. R., “Genetic Programming: On the Programming of Computers by Means of Natural Selection”, MIT Press (1992), incorporated by reference herein, an evolutionary algorithm can be used to evolve complete programs in declarative notation. The basic elements of an evolutionary algorithm are an environment, a model for a genotype (referred to herein as an “individual”), a fitness function, and a procreation function. An environment may be a model of any problem statement. An individual may be defined by a set of rules governing its behavior within the environment. A rule may be a list of conditions followed by an action to be performed in the environment. A fitness function may be defined by the degree to which an evolving rule set is successfully negotiating the environment. A fitness function is thus used for evaluating the fitness of each individual in the environment. A procreation function generates new individuals by mixing rules with the fittest of the parent individuals. In each generation, a new population of individuals is created.
At the start of the evolutionary process, individuals constituting the initial population are created randomly, by putting together the building blocks, or alphabets, that form an individual. In genetic programming, the alphabets are a set of conditions and actions making up rules governing the behavior of the individual within the environment. Once a population is established, it is evaluated using the fitness function. Individuals with the highest fitness are then used to create the next generation in a process called procreation. Through procreation, rules of parent individuals are mixed, and sometimes mutated (i.e., a random change is made in a rule) to create a new rule set. This new rule set is then assigned to a child individual that will be a member of the new generation. In some incarnations, known as elitist methods, the fittest members of the previous generation, called elitists, are also preserved into the next generation.
After evolution, a typical evolutionary algorithm system will yield a set of at least two individuals, each of which has performed well during their fitness evaluations. In some evolutionary algorithm systems they all represent different solutions to the same problem. In such evolutionary algorithm systems all the resulting individuals take the same set of inputs, and assert the same set of outputs, though the rules by which they assert an output based on the inputs may be different. In other evolutionary algorithm systems some portion of the resulting individuals solves a different problem than others, for example they assert a different set of outputs based on the same set of inputs. For example they may all take temperature and time-cost-of-energy as inputs, but some may assert a signal to control an electric heater whereas others assert a signal to control a gas furnace. In such evolutionary algorithm systems the different individuals might have been evaluated with different fitness functions, each designed to encourage optimum control of the respective heating system (i.e., the gas furnace, and electric heater). In yet other evolutionary algorithm systems, different subsets of the individuals may take different sets of inputs into account, though they may assert the same outputs. This type of system might result from a class-based evolution process, in which different subsets of indicators are provided as inputs to different subsets of individuals being evaluated, though the fitness function used to evaluate them is the same. In yet other systems, the individuals are all trained on the same set of inputs and assert the same outputs, but they are deployed in different environments, so that in operation they receive different values on their inputs. This might be case, for example, where a set of individuals are evolved for controlling electrical appliances of a household, but the identical set is deployed to multiple households. Still further systems can have combinations of the above variations.
The above information is presented as background information only to assist with an understanding of the present disclosure. No determination has been made, and no assertion is made, as to whether any of the above might be applicable as prior art with regard to the present disclosure.